1. Field of the Invention
The present invention relates to a method of determining whether a virtual address corresponds to a physical address in a translation lookaside buffer.
2. Description of the Prior Art
Memory has become an essential device in computer systems. How to access data stored in memory efficiently and quickly is an important problem that concerns those skilled in the art. When a CPU accesses data stored in the memory, it must send a memory address for pointing out what part of the memory stores the data that is to be accessed. It seems that the memory is assumed to be composed of a plurality of memory units which have their own addresses. These addresses in the memory are called physical addresses. However, when the CPU of a normal computer accesses the memory, the CPU sends the virtual address instead of physical address for representing the address of the memory where the data is stored. The virtual address is translated into the physical address through a specific method, which is accomplished by a translation lookaside buffer (TLB). Translating the virtual address into the physical address for accessing the memory can make the memory in the computer system more elastic and more efficient.
The translation lookaside buffer can be regarded as a big comparing table. One side of the comparing table comprises the virtual addresses of the CPU, the other side of the comparing table comprises the physical addresses, and the translation lookaside buffer determines the corresponding relationship between the physical addresses and the virtual addresses. When the CPU accesses the data of a specific address of a memory, the CPU first compares the specific address with the virtual addresses in the comparing table, and then finds out the corresponding physical address for accessing the data. The translation lookaside buffer is usually set up in a cache memory for quickly mapping. The mapping method of the translation lookaside buffer is shown in FIG. 1, which is a diagram of a mapping method of a translation lookaside buffer with various page sizes according to the prior art. The method can be divided into three parts. The first part is “comparing bits”, the second part is “decoding bits”, and the third part is referred to as “Page”. The mapping method of the translation lookaside buffer utilizes a page as a unit instead of a single memory. A page is composed of a series of memories, and the addresses of the memories in the same page have the same leading bits. The comparing bits can be regarded as the page number of different pages. The decoding bits are the index of a certain related entry. In the procedure of comparing, the decoding bits are first utilized for finding out the entries of the corresponding relationships stored in the translation lookaside buffer and determining an entry, and then the comparing bits are utilized for comparing and finding out the page number so that the corresponding page is determined. The translation lookaside buffer only has to handle the comparing bits and decoding bits, and the memories of the page can be appropriately executed through the direct accessing method.
However, for a translation lookaside buffer which has various page sizes, the page sizes are not fixed. For example, the page sizes can be 1 k bits, 4 k bits, 64 k bits, 1M bits, or the like. In FIG. 1, a 32-bit translation lookaside buffer and the distribution of the bits in the translation lookaside buffer with four different page sizes are shown. A page of a 1 k-bit page size has 10 bits that are respectively from the 0th bit to the 9th bit. If the corresponding relationship that is to be determined by the decoding bits has 64 different entries, 4 bits are needed so that from the 12th bit to the 15th bit are the decoding bits. The 18 bits left are therefore comparing bits. Besides, the page of a 64 k-bit page size has 16 bits that are respectively from the 0th bit to the 15th bit. The decoding bits are from the 16th bit to 19th bit, and the comparing bits are from the 20th bit to 31st bit. Other sizes may be deduced by analogy.
Please refer to FIG. 2, which is a block diagram of the translation lookaside buffer 10 according to the prior art. The translation lookaside buffer 10 comprises four related memory blocks 12, four data memory blocks 14, and a multiplexer 16. The decoding bits and the comparing bits of the virtual address are inputted into the related memory blocks 12. The comparing bits are compared with a memory content selected by the decoding bits in the related memory blocks 12, and then the comparing results are inputted into the multiplexer 16. At the same time, the decoding bits also selects the physical address in the data memory blocks 14 that corresponds to the virtual address and outputs the results into the multiplexer 16.
Although the prior art translation lookaside buffer can efficiently complete the mapping between the virtual addresses and the physical addresses, the hardware equipment is complicated and the cost is high because of the method of parallel processing for comparing bits of different entries. Furthermore, a memory with many ports is needed to implement the above-mentioned structure so that the complexity of the design is higher. And then, when the prior art compares different page sizes, each page capacity needs a translation lookaside buffer shown in FIG. 2. This means that four page sizes need four translation lookaside buffers. Apparently, for the translation lookaside buffer used for different page sizes, the prior art hardware required is increased in a direct proportion so that the hardware can not be efficiently utilized for completing the translation between the virtual address and the physical address.